package top.dprkshow.practice.graph;

import java.util.List;
import java.util.Stack;

/**
 * @author Kent HAN
 * @date 2021/9/9
 */
public class DfsPaths {

    private boolean[] visited;
    private int[] edgeTo;
    private final int source;

    public DfsPaths(Digraph graph, int source) {
        visited = new boolean[graph.getTotalVertices()];
//        edgeTo = new int[graph.getTotalVertices()];
        validateVertex(source);
        this.source = source;
//        dfs(graph, source);
//        dfsStack(graph, source);
        dfsDigraph(graph, source);
    }

    public void dfsDigraph(Digraph graph, int source) {
        visited[source] = true;
        for (Integer adjVertex : graph.adj(source)) {
            if (!visited[adjVertex]) {
                dfsDigraph(graph, adjVertex);
            }
        }
    }

    private void dfs(MatrixGraph graph, int source) {
        visited[source] = true;
        for (int adjVertex : graph.adj(source)) {
            if (!visited[adjVertex]) {
                edgeTo[adjVertex] = source;
                dfs(graph, adjVertex);
            }
        }
    }

    private void dfsStack(MatrixGraph graph, int source) {
        Stack<Integer> stack = new Stack<>();
        visited[source] = true;
        stack.push(source);
        while (!stack.isEmpty()) {
            Integer s = stack.pop();
            for (Integer adjVertex : graph.adj(s)) {
                if (!visited[adjVertex]) {
                    visited[adjVertex] = true;
                    edgeTo[adjVertex] = s;
                    stack.push(adjVertex);
                }
            }
        }
    }

    private void validateVertex(int vertex) {
        if (vertex < 0 || vertex >= visited.length) {
            throw new IllegalArgumentException("vertex " + vertex + " is not between 0 and " + (vertex - 1));
        }
    }
}
